#include <iostream>
#include <vector>
#include <deque>

using namespace std;
// 103. 二叉树的锯齿形层序遍历
// 给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。
// （即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode():val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x):val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right): val(x), left(left), right(right) {}
};
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(root == nullptr)
            return res;

        deque<TreeNode*> q;
        q.push_back(root);  // 根节点入队列
        bool flag = true;   // flag为true表示从左往右遍历，为false表示从右往左遍历
        while(!q.empty()) {
            size_t sz = q.size();
            deque<int> levelNodes;
            for(size_t i = 0; i < sz; i++) {
                TreeNode* head = q.front();
                q.pop_front();
                if(flag)
                    levelNodes.push_back(head->val);
                else
                    levelNodes.push_front(head->val);

                if(head->left != nullptr)
                    q.push_back(head->left);
                if(head->right != nullptr)
                    q.push_back(head->right);
            }
            flag = !flag;
            vector<int> tmpres(levelNodes.begin(),levelNodes.end());
            res.push_back(tmpres);
        }
        return res;
    }
};
void printRes(vector<vector<int>>& res) {
    cout << "[";
    for(int i = 0; i < res.size(); i++) {
        cout << "[";
        for(int j = 0; j < res[i].size(); j++) {
            cout << res[i][j];
            if(j < res[i].size() - 1)
                cout << ",";
        }
        cout << "]";
        if(i < res.size() - 1)
            cout << ",";
    }
    cout << "]" << endl;
}

int main() {
    TreeNode* root1 = new TreeNode(3,new TreeNode(9),new TreeNode(20,
                                                                  new TreeNode(15),new TreeNode(7)));
    vector<vector<int>> res1 = Solution().zigzagLevelOrder(root1);
    printRes(res1);
    return 0;
}
